// Created by WXX on 2021/11/30 15:55
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

/**
 * 执行用时：192 ms, 在所有 C++ 提交中击败了76.58%的用户
 * 内存消耗：100.9 MB, 在所有 C++ 提交中击败了80.18%的用户
 */
const int N = 100000;

int son[N][26], cnt[N], idx;

class StreamChecker {
public:

    void insert(string str) {
        int p = 0;
        for (int i = 0; str[i]; i++) {
            int u = str[i] - 'a';
            if (!son[p][u]) son[p][u] = ++idx;
            p = son[p][u];
        }
        cnt[p]++;
    }

    StreamChecker(vector<string>& words) {
        memset(son, 0, sizeof son);
        memset(cnt, 0, sizeof cnt);
        idx = 0;

        for (auto word : words) {
            reverse(word.begin(), word.end());
            insert(word);
        }
    }

    string s;
    bool query(char letter) {
        s += letter;

        int p = 0;
        for (int i = s.size() - 1; i >= 0; i--) {
            int u = s[i] - 'a';
            if (!son[p][u]) return false;
            p = son[p][u];
            if (cnt[p]) return true;
        }
        return false;
    }
};

int main() {


    return 0;
}
